/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-07-08
 * Time: 11:16
 */
//冒泡排序算法，这是一种稳定的排序方法。
// 它的基本思想是：比较相邻的元素，如果前一个比后一个大，就交换他们两个。
    //从0~n-1的范围不断缩小，在每一个范围内，比较相邻的元素，如果前一个比后一个大，就交换他们两个。
    //时间复杂度：O(n^2)，空间复杂度：O(1)
public class BubbleSort {
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    private static void printArray(int[] arr) {
        for (int j : arr) {
            System.out.print( j + " " );
        }
        System.out.println();
    }
    //第一种方法
    private static void bubbleSort(int[] arr){
        int n = arr.length;
        for(int i=0;i<n;i++){
            for(int j=0;j<n-i-1;j++){
                if(arr[j]>arr[j+1]){
                    swap( arr, j, j+1);
                }
            }
        }
    }
    //第一种方法的优化版本，对已经排序的数据进行优化，避免了每次都要从头开始比较的开销
    private static void bubbleSort2(int[] arr){
        int n = arr.length;
        for(int i=0;i<n;i++){
            boolean flag = false;
            for(int j=0;j<n-i-1;j++){
                if(arr[j]>arr[j+1]){
                    swap( arr, j, j+1);
                    flag = true;
                }
            }
            //如果没有发生交换，说明数据已经是从小到大有序的，可以直接退出循环
            if(!flag){
                break;
            }
        }
    }
    //第二种方法
    private static void bubbleSort3(int[] arr) {
        int n=arr.length;
        //数组无序的范围变化
        //0~n-1
        //0~n-2
        //0~n-3
        //从后往前缩小范围，直到全部有序
        for(;n>=0;n--){
            //在每一个范围内干一个事，就是从下标1开始，比较他和前一个元素的大小
            for(int j=1;j<n;j++){
                if(arr[j]<arr[j-1]){
                    swap(arr,j,j-1);
                }
            }
        }
    }
    public static void main (String[] args) {
        int[] arr={1,3,5,7,9,2,4,6,8,0};
        printArray(arr);
        //bubbleSort(arr);
        //bubbleSort2( arr );
        bubbleSort3( arr );
        printArray(arr);
    }
}
